package 单周赛.september;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @
 * @date 2024/10/20
 */
public class 第420场单周赛 {

    public static void main(String[] args) {

        System.out.println(stringSequence("z"));

        第420场单周赛 impl = new 第420场单周赛();
        impl.numberOfSubstrings("abacb", 2);

        impl.collectPrime(1000000);
        System.out.println(impl.primes.size());
    }

    public static List<String> stringSequence(String target) {

        List<String> list = new ArrayList<>();
        while (list.isEmpty() || !target.equals(list.get(list.size() - 1))) {
            if (list.isEmpty()) {
                list.add("a");
                continue;
            }

            String lastStr = list.get(list.size() - 1);
            int lastIdx = lastStr.length() - 1;
            if (lastStr.charAt(lastIdx) != target.charAt(lastIdx)) {
                char lastChar = lastStr.charAt(lastIdx);
                StringBuilder stringBuilder = new StringBuilder()
                        .append(lastStr);
                stringBuilder.setCharAt(lastIdx, (char) (((lastChar - 'a') + 1) % 26 + (int) 'a'));
                list.add(stringBuilder.toString());
            } else {
                list.add(lastStr + "a");
            }
        }

        return list;
    }

    public int numberOfSubstrings(String s, int k) {
        int ans = 0;
        int[] record = new int[26];
        int left = 0, right = 0;

        while (left < s.length()) {

            while (right < s.length() && !isK(record, k)) {
                record[s.charAt(right) - 'a']++;
                right++;
            }
            if (isK(record, k)) {
                ans += s.length() - right + 1;
            }

            record[s.charAt(left) - 'a']--;
            left++;
        }
        return ans;
    }

    private boolean isK(int[] record, int k) {
        for (int i : record) {
            if (i >= k) {
                return true;
            }
        }
        return false;
    }

    public int minOperations(int[] nums) {
        collectPrime(Arrays.stream(nums).max().getAsInt());
        if (nums.length == 1) {
            return 0;
        }
        int ans = 0;
        for (int i = nums.length - 2; i >= 0; i--) {

            if (nums[i] <= nums[i + 1]) {
                continue;
            }

            while (nums[i] > nums[i + 1]) {
                int curNum = findYS(nums[i]);
                ans++;
                if (curNum == -1) {
                    return -1;
                }
                nums[i] = curNum;
            }
        }

        return ans;
    }

    private int findYS(int num) {
        for (Integer prime : primes) {
            if (prime >= num) {
                return -1;
            }
            if (num % prime == 0) {
                return prime;
            }
        }
        return 0;
    }

    List<Integer> primes = new ArrayList<>();

    private void collectPrime(int max) {
        boolean[] record = new boolean[max + 1];
        for (int num = 2; num <= max; num++) {
            if (!record[num]) {
                primes.add(num);
            }

            int c = num;
            while ((long) num * c <= max) {
                record[num * c] = true;
                c++;
            }
        }
    }
}
